package com.foxzzz.greedy;

public class Solution45 {
    public int jump(int[] nums) {
        int max = 0;
        int step = 0;
        int preMax = 0;
        if (nums.length > 1) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = i; j < preMax  + 1 && j < nums.length; j++) {
                    max = Math.max(max, j + nums[j]);
                }
                if (preMax != max) {
                    step++;
                }
                preMax = max;
                if (max + 1 >= nums.length) {
                    break;
                }
            }
        }
        return step;
    }

    public static void main(String[] args) {
        System.out.println(new Solution45().jump(new int[]{1, 2, 3, 4, 5}));
        //3
        System.out.println(new Solution45().jump(new int[]{1, 2, 1, 1, 1}));
        //3
        System.out.println(new Solution45().jump(new int[]{1, 1, 1, 1}));
        //2
        System.out.println(new Solution45().jump(new int[]{2, 3, 1, 1, 4}));

    }
}

